% author: Starrysky
% last update date: 2022-10-09
% description: 以 UTF-8 编码保存, 使用 XeLaTeX 编译

% 使用CTex宏集以支持中文
\documentclass[UTF8]{ctexart}
% 从此处到正文开始前是导言区, 进行文档全局设置
% 设置页面大小和页边距
\usepackage[a4paper, margin=1in, bottom=0.5in]{geometry}
% 支持数学公式
\usepackage{amsmath}
% 支持超链接
\usepackage{hyperref}
% 支持图片
\usepackage{graphicx}
% 设置图片文件目录
\graphicspath{{./resources}}
% 支持伪代码
\usepackage{algorithm}
\usepackage{algorithmic}
% 替换为Input和Output
\renewcommand{\algorithmicrequire}{\textbf{Input:}}
\renewcommand{\algorithmicensure}{\textbf{Output:}}

\title{整数规划\quad 书面作业}
\author{方仕元\quad 202228013229063}
\date{\today}
% 正文部分
\begin{document}

% 显示导言区设置的title、author、date等信息
\maketitle
% 显示目录，目录要编译两次
\tableofcontents
% 分页
\newpage

% 多级section、paragraph的排版
\section{Question 1}
\paragraph{Solution}

设$x_{ij}$的含义为: 是否分配第$i$号工人去完成第$j$号工作；若分配，则$x_{ij}=1$;若不分配,则$x_{ij}=0$。
则求解原问题可用如下不等式组表示:
\begin{align*}
	  \emph{to minimize:} \quad &  \sum x_{ij} \cdot C_{ij}  \\
	  \emph{s.t.} \quad & \forall x_{ij},1 \le i \le m, 1\le j \le n : x_{ij}\in \{0,1\} \\
	  & \forall j, 1\le j\le n: \sum_{i=1}^{m} x_{ij} = 1\\
\end{align*}

\section{Question 2}
\paragraph{Solution}

设$A_j$的含义为: 第$j$号营养素的所需量。设$x_i$的含义为: 第$i$号食物的摄入量。

则求解原问题可用如下不等式组表示:

\begin{align*}
	\emph{to minimize:} \quad &  \sum x_{i} \cdot C_{i}  \\
	\emph{s.t.} \quad & \forall x_i,1 \leq i \leq m : x_i \geq 0 \\
	& \forall j, 1\le j \le n : \sum_{i=1}^{m} x_i\cdot W_{ij} \geq A_j \\
\end{align*}

\section{Question 3}
\paragraph{Solution}
设$x_{ij}$的含义为: 从$i$号供货地到$j$号市场的货运量。

则求解原问题可用如下不等式组表示:
\begin{align*}
	\emph{to minimize:} \quad & \sum x_{ij}\cdot C_{ij} \\
	\emph{s.t.} \quad & \forall j, 1 \leq j \leq m:\sum_{i=1}^{n} x_{ij}=b_j \\
	& \forall i,1 \leq i\leq n: \sum_{j=1}^{m} x_{ij} \leq a_i
\end{align*}

\section{Question 4}
\paragraph{Solution}
设$x_{ij}$的含义为: 是否把第$i$号物品放入第$j$号盒子; 若放入则$x_{ij}=1$, 否则$x_{ij}=0$。设$y_j$的含义为: 第$j$号盒子是否被使用; 若被使用则$y_j=1$, 否则$y_j=0$。

则求解原问题可用以下不等式组表示:
\begin{align*}
	\emph{to minimize:} \quad & \sum_{j=1}^{n} y_j \\
	\emph{s.t.} \quad & \forall i,1 \leq i\leq m: \sum_{j=1}^{n} x_{ij}=1 \\
	& \forall j, 1 \leq j \leq n: \sum_{i=1}^{m} x_{ij}\cdot C_i \leq S_j \\
	& \forall j, 1\leq j \leq n: y_j=\max_{i=1}^{m} x_{ij} \\
	& \forall x_{ij},1\leq i \leq m, 1\leq j \leq n:x_{ij}\in \{0,1\} \\
\end{align*}

\section{Question 6}
\paragraph{Solution}
设$x_i$的含义为: 是否投资第$i$号项目;若投资, 则$x_i=1$; 否则$x_i=0$。

则求解原问题可用以下不等式组表示:
\begin{align*}
	\emph{to maximize:} \quad & \sum_{j=1}^{n} x_j\cdot c_j \\
	\emph{s.t.} \quad & \forall x_j,1 \leq j \leq n:x_j\in\{0,1\} \\
	& \sum_{j=1}^{n} x_j\cdot b_j \leq B \\
\end{align*}

\section{Question 7}
\paragraph{Solution}
设$a,b$分别为A类宿舍和B类宿舍的建造数量。

则求解原问题等价于求解以下不等式组:
\begin{align*}
	\emph{to maximize:} \quad & a\cdot c_i + b\cdot c_j \\
	\emph{s.t.} \quad & a,b \in \textbf{自然数集} \\
	& 0 \leq a\leq n_i \\
	& 0\leq b\leq n_j \\
	& a\cdot s_i +b\cdot s_j \leq s
\end{align*}

\section{Question 8}
\paragraph{Solution}
设$x_i$的含义为: 是否选择在第$i$号地点开张; 若选中, 则$x_i=1$; 否则$x_i=0$。

则求解原问题等价于求解以下不等式组:
\begin{align*}
	\emph{to maximize:} \quad & \sum_{i=1}^{7} x_i\cdot c_i \\
	\emph{s.t.} \quad & \forall x_i,  0 \leq i\leq 7: x_i \in\{0,1\} \\
	& \sum_{i=1}^{7} x_i\cdot b_i \leq B \\
	& x_1+x_2+x_3\leq 2 \\
	& x_4+x_5\geq 1 \\
	& x_6+x_7\geq 1\\
\end{align*}

\section{Question 9}
\paragraph{Solution}
设$x_j$的含义为: 是否选择第$i$号物品装入背包。若选中，则$x_j=1$;否则$x_j=0$。

则求解原问题等价于求解以下不等式组:
\begin{align*}
	\emph{to maximize:} \quad & \sum_{j=1}^{n} x_j\cdot c_j \\
	\emph{s.t.} \quad & \forall x_j, 1\leq j\leq n: x_j \in \{0,1\} \\
	& \sum_{j=1}^{n} x_j\cdot a_j \leq b \\
\end{align*}


\end{document}